{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Middle Index in Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMiddleIndex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到数组的中间位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，请你找到 <strong>最左边</strong>&nbsp;的中间位置&nbsp;<code>middleIndex</code>&nbsp;（也就是所有可能中间位置下标最小的一个）。</p>\n",
    "\n",
    "<p>中间位置&nbsp;<code>middleIndex</code>&nbsp;是满足&nbsp;<code>nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1]</code>&nbsp;的数组下标。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>middleIndex == 0</code>&nbsp;，左边部分的和定义为 <code>0</code>&nbsp;。类似的，如果&nbsp;<code>middleIndex == nums.length - 1</code>&nbsp;，右边部分的和定义为&nbsp;<code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回满足上述条件 <strong>最左边</strong>&nbsp;的<em>&nbsp;</em><code>middleIndex</code>&nbsp;，如果不存在这样的中间位置，请你返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,3,-1,<em><strong>8</strong></em>,4]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "下标 3 之前的数字和为：2 + 3 + -1 = 4\n",
    "下标 3 之后的数字和为：4 = 4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,-1,<em><strong>4</strong></em>]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "下标 2 之前的数字和为：1 + -1 = 0\n",
    "下标 2 之后的数字和为：0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,5]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>\n",
    "不存在符合要求的 middleIndex 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [<em><strong>1</strong></em>]\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "下标 0 之前的数字和为：0\n",
    "下标 0 之后的数字和为：0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与主站 724 题相同：<a href=\"https://leetcode-cn.com/problems/find-pivot-index/\" target=\"_blank\">https://leetcode-cn.com/problems/find-pivot-index/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-middle-index-in-array](https://leetcode.cn/problems/find-the-middle-index-in-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-middle-index-in-array](https://leetcode.cn/problems/find-the-middle-index-in-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,-1,8,4]', '[1,-1,4]', '[2,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMiddleIndex(self, nums: List[int]) -> int:\n",
    "        leftSum, rightSum = 0, sum(nums[i] for i in range(1, len(nums)))\n",
    "        if leftSum == rightSum:\n",
    "            return 0\n",
    "\n",
    "        for middleIndex in range(1, len(nums)):\n",
    "            leftSum += nums[middleIndex - 1]\n",
    "            rightSum -= nums[middleIndex]\n",
    "\n",
    "            if leftSum == rightSum:\n",
    "                return middleIndex\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMiddleIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if sum(nums[:i]) == sum(nums[i+1:]):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMiddleIndex(self, nums: List[int]) -> int:\n",
    "        S = sum(nums)\n",
    "        left = 0\n",
    "        if S - nums[0] == 0:\n",
    "            return 0\n",
    "        for i in range(1, len(nums)):\n",
    "            left += nums[i-1]\n",
    "            if S - nums[i] == 2*left:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMiddleIndex(self, nums: List[int]) -> int:\n",
    "        target = sum(nums)\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if ans*2+nums[i] == target:\n",
    "                return i\n",
    "            ans += nums[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMiddleIndex(self, nums: List[int]) -> int:\n",
    "        chang = len(nums)\n",
    "        #res = 0\n",
    "        for i in range(chang):\n",
    "            print(i, sum(nums[0:i]),sum(nums[i+1:]))\n",
    "            if sum(nums[0:i]) == sum(nums[i+1:]):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMiddleIndex(self, nums: List[int]) -> int:\n",
    "        lenth = len(nums)\n",
    "        total = sum(nums)\n",
    "        left = 0\n",
    "        for i in range(lenth):\n",
    "            if left == (total - nums[i])/2:\n",
    "                return i\n",
    "            else:\n",
    "                left = left + nums[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMiddleIndex(self, nums: List[int]) -> int:\n",
    "        # sum = 0\n",
    "        # l = len(nums)\n",
    "        # for i in range(l):\n",
    "        #     sum += nums[i]\n",
    "        # if sum - nums[0] == 0:\n",
    "        #     return 0\n",
    "        # for i in range(1,l):\n",
    "        #     left_sum = right_sum = 0\n",
    "        #     for m in range(i):\n",
    "        #         left_sum += nums[m]\n",
    "        #     for n in range(i + 1, l):\n",
    "        #         right_sum += nums[n]\n",
    "        #     if left_sum == right_sum:\n",
    "        #         return i\n",
    "        # if sum - nums[l - 1] == 0:\n",
    "        #     return (l - 1)\n",
    "        # return -1\n",
    "        total = sum(nums)\n",
    "        left_sum = 0\n",
    "        right_sum  = 0\n",
    "        for i in range(len(nums)):\n",
    "            left_sum += nums[i]\n",
    "            right_sum = total - left_sum\n",
    "            if left_sum - nums[i] == right_sum:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMiddleIndex(self, nums: List[int]) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 0-indexed 的整數 array: nums\n",
    "        找最左邊的 middleIndex\n",
    "        \n",
    "        middleIndex 的意思是:\n",
    "        nums[0] + nums[1] + ... + nums[middleIndex] = nums[middleIndex + 1] + ... + nums[-1]\n",
    "\n",
    "        1. 如果 middleIndex = 0, 代表左側的總和是 0\n",
    "        2. 如果 middleIndex = len(nums) - 1, 代表右側的總和是 0\n",
    "        如果都找不到, 回傳 -1\n",
    "        \"\"\"\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            left_sum  = sum(nums[:i])\n",
    "            right_sum = sum(nums[i + 1:])\n",
    "            if left_sum == right_sum:\n",
    "                return i\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
